package
{
	import flash.utils.ByteArray;
	
	public class Map
	{
		public var rowCount:uint;
		public var columnCount:uint;
		public var cells:Vector.<Vector.<int>>;
		public var terrain:Vector.<Vector.<Terrain>>;
		public var objects:Vector.<Vector.<MapObject>>;
		public static var cellSize:uint = 32;
		public function Map()
		{
			
		}
		public function SetValueFromSize(row:uint,column:uint):void
		{
			rowCount = row;
			columnCount = column;
			cells = new Vector.<Vector.<int>>(rowCount);
			//cells = new Array(rowCount);
			for(var i:int = 0;i<cells.length;i++)
			{
				cells[i] = new Vector.<int>(columnCount);
				//cells[i] = new Array(columnCount);
			}
			for(i = 0;i<rowCount;i++)
			{
				for(var j:int = 0;j<columnCount;j++)
				{
					cells[i][j] = 0;
				}
			}
		}
		public function SetValueFromByteArray(data:ByteArray):void
		{
			rowCount = data.readUnsignedByte();
			columnCount = data.readUnsignedByte();
			cells = new Vector.<Vector.<int>>(rowCount);
			for(var i:int = 0;i<cells.length;i++)
			{
				cells[i] = new Vector.<int>(columnCount);
			}
			for(i = 0;i<rowCount;i++)
			{
				for(var j:int = 0;j<columnCount;j++)
				{
					cells[i][j] = data.readUnsignedByte();
				}
			}
			terrain = new Vector.<Vector.<Terrain>>(rowCount);
			for(i = 0;i<terrain.length;i++)
			{
				terrain[i] = new Vector.<Terrain>(columnCount);
			}
			for(i = 0;i<rowCount;i++)
			{
				for(var j:int = 0;j<columnCount;j++)
				{
					var id:uint = data.readUnsignedInt();
					if(id > 0)
					{
						terrain[i][j] = new Terrain(id,null);
					}
				}
			}
			objects = new Vector.<Vector.<MapObject>>(rowCount);
			for(i = 0;i<terrain.length;i++)
			{
				objects[i] = new Vector.<MapObject>(columnCount);
			}
			for(i = 0;i<rowCount;i++)
			{
				for(var j:int = 0;j<columnCount;j++)
				{
					var id:uint = data.readUnsignedInt();
					if(id > 0)
					{
						objects[i][j] = new MapObject(id,null);
					}
				}
			}
		}
		
		public function Calculate(start:CellPos,dest:CellPos):Vector.<CellPos>
		{
			// linh canh
			if(start.Equal(dest))
			{
				return null;
			}
			var result:Vector.<CellPos> = new Vector.<CellPos>();
			var temp:Vector.<Vector.<Number>> = new Vector.<Vector.<Number>>(this.rowCount+2);
			var maxValue:int = this.columnCount*this.rowCount*2;
			for(var i:int = 0;i<this.rowCount+2;i++)
			{
				temp[i] = new Vector.<Number>(this.columnCount + 2);
				for(var j:int = 0;j<this.columnCount + 2;j++)
				{
					temp[i][j] = maxValue;
				}
			}
			temp[start.Row + 1][start.Column + 1] = 0;
			/*
			var range:uint = 0;
			while((start.Column + range < this.columnCount - 1) || (start.Column - range > 0)
					|| (start.Row + range < this.rowCount - 1) || (start.Row - range > 0))
			{
				range++;
				for(i = Math.max(0,start.Column - range);i<Math.min(this.columnCount,start.Column + range);i++)
				{
					if(start.Row - range >= 0)
					{
						CalculateCell(new CellPos(start.Row - range,i),temp);
					}
					if(start.Row + range < this.rowCount)
					{
						CalculateCell(new CellPos(start.Row + range,i),temp);
					}
				}
				if(temp[dest.Row + 1][dest.Column + 1] < maxValue)
				{
					break;
				}
			}
			*/
			result.push(start);
			while(true)
			{
				var clone:Vector.<CellPos> = new Vector.<CellPos>();
				var cell:CellPos;
				for(i=0;i<result.length;i++)
				{
					if(result[i].Row - 1 >= 0 && this.cells[result[i].Row - 1][result[i].Column] != 0 
						&& temp[result[i].Row][result[i].Column + 1] == maxValue )
					{
						cell = new CellPos(result[i].Row - 1, result[i].Column);
						CalculateCell(cell,temp);
						clone.push(cell);
					}
					if(result[i].Row + 1 < this.rowCount && this.cells[result[i].Row + 1][result[i].Column] != 0 
						&& temp[result[i].Row + 2][result[i].Column + 1] == maxValue )
					{
						cell = new CellPos(result[i].Row + 1, result[i].Column);
						CalculateCell(cell,temp);
						clone.push(cell);
					}
					if(result[i].Column - 1 >= 0 && this.cells[result[i].Row][result[i].Column - 1] != 0 
						&& temp[result[i].Row + 1][result[i].Column] == maxValue )
					{
						cell = new CellPos(result[i].Row, result[i].Column - 1);
						CalculateCell(cell,temp);
						clone.push(cell);
					}
					if(result[i].Column + 1 < this.columnCount && this.cells[result[i].Row][result[i].Column + 1] != 0 
						&& temp[result[i].Row + 1][result[i].Column + 2] == maxValue )
					{
						cell = new CellPos(result[i].Row, result[i].Column + 1);
						CalculateCell(cell,temp);
						clone.push(cell);
					}
				}
				result = clone;
				if(result.length == 0 || temp[dest.Row+1][dest.Column+1] < maxValue)
				{
					break;
				}
			}
			if(temp[dest.Row+1][dest.Column+1] == maxValue)
			{
				return null;
			}
			//-----------------
			result = new Vector.<CellPos>();
			result.push(dest);
			while(true)
			{
				var cell:CellPos = FindShortestCell(result[result.length-1],temp);
				if(cell.Equal(start))
				{
					break;
				}
				result.push(cell);
			}
			return result;
		}
		protected function CalculateCell(pos:CellPos, value:Vector.<Vector.<Number>>):void
		{
			if(cells[pos.Row][pos.Column] == 0)
			{
				return;
			}				
			var t1:Number;
			var t2:Number;
			var p:CellPos = new CellPos(pos.Row + 1,pos.Column + 1);
			t1 = 1 + Math.min(value[p.Row][p.Column + 1],value[p.Row][p.Column - 1],value[p.Row + 1][p.Column],value[p.Row - 1][p.Column]);
			t2 = 1.41421356 + Math.min(value[p.Row + 1][p.Column + 1],value[p.Row - 1][p.Column - 1],value[p.Row - 1][p.Column + 1],value[p.Row + 1][p.Column - 1]);
			value[p.Row][p.Column] = Math.min(t1,t2);
		}
		protected function FindShortestCell(cell:CellPos, value:Vector.<Vector.<Number>>):CellPos
		{
			var t:CellPos = new CellPos(cell.Row+1,cell.Column+1);
			var shortest:CellPos = new CellPos(t.Row-1,t.Column);

			if(value[t.Row + 1][t.Column] < value[shortest.Row][shortest.Column])
			{
				shortest = new CellPos(t.Row + 1,t.Column);
			}
			if(value[t.Row][t.Column - 1] < value[shortest.Row][shortest.Column])
			{
				shortest = new CellPos(t.Row,t.Column - 1);
			}
			if(value[t.Row][t.Column + 1] < value[shortest.Row][shortest.Column])
			{
				shortest = new CellPos(t.Row,t.Column + 1);
			}
			//0.414213562
			if(value[t.Row - 1][t.Column - 1] < value[shortest.Row][shortest.Column])
			{
				shortest = new CellPos(t.Row - 1,t.Column - 1);
			}
			if(value[t.Row + 1][t.Column + 1] < value[shortest.Row][shortest.Column])
			{
				shortest = new CellPos(t.Row + 1,t.Column + 1);
			}
			if(value[t.Row - 1][t.Column + 1] < value[shortest.Row][shortest.Column])
			{
				shortest = new CellPos(t.Row - 1,t.Column + 1);
			}
			if(value[t.Row + 1][t.Column - 1] < value[shortest.Row][shortest.Column])
			{
				shortest = new CellPos(t.Row + 1,t.Column - 1);
			}
			return new CellPos(shortest.Row-1,shortest.Column-1);
		}
	}
}